#include <iostream>
#include <set>

using namespace std;

class MedianFinder {
private:
    multiset<int, greater<int>> small;
    multiset<int> big;
public:
    /** initialize your data structure here. */
    MedianFinder() {}

    void addNum(int num) {
        small.insert(num);
        int val = *small.begin();
        small.erase(small.begin());
        big.insert(val);
        while (big.size() > small.size()) {
            int val = *big.begin();
            big.erase(big.begin());
            small.insert(val);
        }
    }

    double findMedian() {
        if (small.size() > big.size()) {
            return *small.begin();
        } else {
            return (*small.begin() + *big.begin()) / 2.0;
        }
    }
};

int main() {
    MedianFinder medianFinder;
    medianFinder.addNum(1);
    medianFinder.addNum(2);
    double output = medianFinder.findMedian();
    cout << output << endl;
    medianFinder.addNum(3);
    output = medianFinder.findMedian();
    cout << output << endl;
}
